import java.math.BigInteger;
import java.util.Random;
import java.util.Vector;

public abstract class Mathematics {
    
    /**
     * Generates a prime number of a chosen length
     * @param length The size of the prime number
     * @return Returns the generated prime number
     */
    public static BigInteger generatePrime(int length) {
        Random rnd = new Random();
        return BigInteger.probablePrime(length, rnd);
    }
    
    /**
     * Finds a coprime for a given number and within the specified range
     * @param value The value for which a coprime should be found
     * @param max The top range of the coprime search
     * @return Returns the coprime for the given number
     */
    public static BigInteger coprime(BigInteger value, BigInteger max) {
        for(BigInteger x = max.subtract(BigInteger.ONE); x.compareTo(BigInteger.valueOf(2)) > 0; x = x.subtract(BigInteger.ONE))
            if (greatestCommonDivisor(x, value).compareTo(BigInteger.ONE) == 0)
                return x;
        return BigInteger.valueOf(-1);
    }
    
    /**
     * Returns the greatest common divisor between two numbers
     * @param x The first number
     * @param y The second number
     * @return The greatest common divisor between the two given numbers
     */
    public static BigInteger greatestCommonDivisor(BigInteger x, BigInteger y) {
        BigInteger max = BigInteger.ONE;
        BigInteger top = (x.compareTo(y) >= 0) ? x : y;
        BigInteger temp = BigInteger.ONE;
        
        while(temp.compareTo(top) <= 0)
        {
            if(x.mod(temp).equals(BigInteger.ZERO) && y.mod(temp).equals(BigInteger.ZERO))
                max = temp;
            temp = temp.add(BigInteger.ONE);
        }
        
        return max;
    }
    
    /**
     * Returns the greatest common divisor between two numbers
     * @param x The first number
     * @param y The second number
     * @return The greatest common divisor between the two given numbers
     */
    public static int greatestCommonDivisor(int x, int y) {
        int max = 1;
        int top = (x >= y) ? x : y;
        int temp = 1;
        
        while(temp <= top)
        {
            if(x % temp == 0 && y % temp == 0)
                max = temp;
            temp++;
        }
        
        return max;
    }
        
    public static int coprime(int value, int max) {
        for(int x = 1; x < max; x++)
            if(greatestCommonDivisor(x,value) == 1)
                return x;
        return -1;
    }
}